پرش به محتوا

زیرگراف القایی

از ویکی‌پدیا، دانشنامهٔ آزاد

در نظریه گراف، یک زیرگراف القایی گرافی است که مجموعه رئوس آن، زیر مجموعه‌ای از مجموعه رئوس گرافی دیگر باشد با این ویژگی که این زیر گراف دارای تمامی یال‌هایی است که بین رئوس نظیر خود در مجموعه رئوس گراف اولیه موجود هستند.

تعریف

[ویرایش]

فرض می‌کنیم گراف (G = (V, E گرافی دلخواه باشد و مجموعه S باشرط S ⊂ V هر زیر مجموعه دلخواهی از مجموعه رئوس گراف G یعنی V باشد؛ لذا زیرگراف القایی [G[S گرافی است متشکل از رئوس موجود در زیر مجموعه S و یال‌های آن، تمامی یال‌های موجود در E است به شرطی که رئوس هر دوسر یال مذکور در S موجود باشد. این تعریف از زیر گراف القایی در مورد گراف‌های غیر جهت دار، جهت دار و گراف چندگانه نیز صادق است.

زیر گراف القایی G[S] را «زیرگراف القا شده از S در G» یا (در صورتی که در انتخاب مجموعه G ابهامی وجود نداشته باشد) «زیرگراف القا شده S» نیز می‌نامند.

نمونه‌ها

[ویرایش]

انواع مهمی از زیرگراف‌های القایی را می‌توانید در زیر مشاهدده کنید؛

محاسبات

[ویرایش]

مسئله یکریختی زیرگراف القایی، نوعی مسئله از یکریختی است که در آن این امر که می‌توان تشخیص داد آیا گرافی یک زیر گراف القایی از گرافی دیگر است، مورد آزمون و بررسی قرار می‌گیرد. چون این مسئله در بر دارنده مسئله گروهک‌ها به عنوان یک مورد خاص می‌باشد، یک ان‌پی کامل محسوب خواهد شد.[۳]

منابع

[ویرایش]
  1. Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics. Oxford. Second Series, 28 (112): 417–420, doi:10.1093/qmath/28.4.417, MR 0485544
  2. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, doi:10.4007/annals.2006.164.51, MR 2233847.
  3. Johnson, David S. (1985), "The NP-completeness column: an ongoing guide", Journal of Algorithms, 6 (3): 434–451, doi:10.1016/0196-6774(85)90012-4, MR 0800733.